# -*- coding: utf-8 -*-            
# @Time : 2023/12/18 22:27
# @Author  : lining
# @FileName: 二叉搜索树求后继.py
"""
https://leetcode.cn/problems/successor-lcci/
设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回null。
root = [2,1,3], p = 1
输出: 2
"""
class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


node5 = TreeNode(7)
node6 = TreeNode(9)
node2 = TreeNode(8, node5, node6)
node7 = TreeNode(11)
node8 = TreeNode(13)
node3 = TreeNode(12, node7, node8)
# 根节点
node4 = TreeNode(10, node2, node3)
node9 = TreeNode(0)


def find_next(root, value):
    current = 9999
    # 先查找value,找到后如果有右子树，则在右子树的左子树中，没有就直接右子树，如果没有右子树，则在遍历过的，比它大的点里面最小的点
    while root:
        if value > root.value:
            root = root.right
        elif value < root.value:
            current = root if root.value < current else current
            root = root.left
        # =的情况
        else:
            # 先找右子树
            if root.right:
                root = root.right
                while root.left:
                    root = root.left
                return root
            # 没有右子树，则在遍历过的，比它大的点里面最小的点
            return current
    print('没找到这个值')


a = find_next(node4,10)
print(a.value)